package com.zjj.algorithm.learning.atguigu.tree.huffman;

import com.zjj.algorithm.learning.atguigu.tree.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * 创建哈夫曼树
 *
 * @author zjj_admin
 * @date 2022/11/28 21:20
 */
public class HuffmanTree {

    public static void main(String[] args) {
        int[] arr = new int[]{13, 7, 8, 3, 29, 6, 1};
        TreeNode huffmanTree = createHuffmanTree(arr);
        huffmanTree.preOrder();
    }


    /**
     * 构建哈夫曼树
     * @param arr
     * @return
     */
    private static TreeNode createHuffmanTree(int[] arr){
        List<TreeNode> nodes = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            nodes.add(new TreeNode(arr[i]));
        }
        while (nodes.size() > 1){
            //对节点进行排序
            Collections.sort(nodes);
            //获取最小的两个节点
            TreeNode leftNode = nodes.get(0);
            TreeNode rightNode = nodes.get(1);
            //构建新的节点
            TreeNode parentNode = new TreeNode(leftNode.getNo() + rightNode.getNo());
            parentNode.setLeft(leftNode);
            parentNode.setRight(rightNode);

            nodes.remove(leftNode);
            nodes.remove(rightNode);

            nodes.add(parentNode);
        }

        return nodes.get(0);
    }


}
